package com.bolang.onlycode.demo;

import java.util.Arrays;

public class QuickSort1 {
    /**
     * pivot 基准点
     * @param arr
     * @param left
     * @param right
     */
    public static int partition(int[] arr, int left, int right){
        // 找出传入数组中的基准点
        int pivot=arr[left];
        // 定义两个指针，begin和end
        int begin=left;
        int end =right;
        while (begin<end){
            // 从后往前遍历，如果后面大于基准则将end指针前移,直到后面小于基准跳出循环
            while(arr[end]>pivot&&end>begin){
                end--;
            }
            // 不用在这里赋值，直接在后面交换就可以,但是begin指针会后移，那谁来和基准点
            // 做交换呢
            arr[begin]=arr[end];
            // 从前往后遍历,如果前面小于基准，则将begin后移
            while(arr[begin]<=pivot&&begin<end){
                begin++;
            }
            arr[end]=arr[begin];

        }
        // 基准元素归位
        arr[end]=pivot;
        return begin;



    }
    public static void qucikSort(int[] arr, int left, int right){
        if(left<right){
            int pos = partition(arr,left,right);
            qucikSort(arr,left,pos-1);
            qucikSort(arr,pos+1,right);
        }
    }
    // 取第一个基准数万一他是整个数组里最小的为啥没事，
    // 那就在第一次把基准数移好之后，基准数的左边就不用再移了，
    // 后续都是对基准数的右边进行移动基准数递归
    // 如果第一个基准数在中间，那么他将第一个基准数移动好后，
    // 再反复给左边第一个找它合适的位置，直到它左半部分完全有序然后开始让他的右半部分完全有序
    // 再对第一个基准数的右边进行排序，反复之后直到右边完全有序
    public static void main(String[] args) {
        int[] ints ={1,9,7,10,3,2,11,10,9,13};
        qucikSort(ints,0,ints.length-1);
        System.out.println(Arrays.toString(ints));
    }
}
